翻訳と辞書 Words near each other ・ "O" Is for Outlaw ・ "O"-Jung.Ban.Hap. ・ "Ode-to-Napoleon" hexachord ・ "Oh Yeah!" Live ・ "Our Contemporary" regional art exhibition (Leningrad, 1975) ・ "P" Is for Peril ・ "Pimpernel" Smith ・ "Polish death camp" controversy ・ "Pro knigi" ("About books") ・ "Prosopa" Greek Television Awards ・ "Pussy Cats" Starring the Walkmen ・ "Q" Is for Quarry ・ "R" Is for Ricochet ・ "R" The King (2016 film) ・ "Rags" Ragland ・ ! (album) ・ ! (disambiguation) ・ !! ・ !!! ・ !!! (album) ・ !!Destroy-Oh-Boy!! ・ !Action Pact! ・ !Arriba! La Pachanga ・ !Hero ・ !Hero (album) ・ !Kung language ・ !Oka Tokat ・ !PAUS3 ・ !T.O.O.H.! ・ !Women Art Revolution Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク exponential hierarchy ： ウィキペディア英語版 exponential hierarchy In computational complexity theory, the exponential hierarchy is a hierarchy of complexity classes, which is an exponential time analogue of the polynomial hierarchy. As elsewhere in complexity theory, “exponential” is used in two different meanings (linear exponential bounds $2^$ for a constant ''c'', and full exponential bounds $2^$), leading to two versions of the exponential hierarchy:〔Sarah Mocas, Separating classes in the exponential-time hierarchy from classes in ''PH'', Theoretical Computer Science 158 (1996), no. 1–2, pp. 221–231.〕〔Anuj Dawar, Georg Gottlob, Lauri Hella, Capturing relativized complexity classes without order, Mathematical Logic Quarterly 44 (1998), no. 1, pp. 109–122.〕 *EH is the union of the classes $\backslash Sigma^E\_k$ for all ''k'', where $\backslash Sigma^E\_k=\backslash mathrm^$ for some constant ''c'' with a $\backslash Sigma^P\_$ oracle). One also defines $\backslash Pi^E\_k=\backslash mathrm^\}$. An equivalent definition is that a language ''L'' is in $\backslash Sigma^E\_k$ if and only if it can be written in the form ::$x\backslash in\; L\backslash iff\backslash exists\; y\_1\backslash ,\backslash forall\; y\_2\backslash dots\; Qy\_k\backslash ,R(x,y\_1,\backslash dots,y\_k),$ :where $R(x,y\_1,\backslash dots,y\_n)$ is a predicate computable in time $2^$ (which implicitly bounds the length of ''yi''). Also equivalently, EH is the class of languages computable on an alternating Turing machine in time $2^$ for some ''c'' with constantly many alternations. *EXPH is the union of the classes $\backslash Sigma^\_k$, where $\backslash Sigma^\_k=\backslash mathrm^$ for some constant ''c'' with a $\backslash Sigma^P\_$ oracle), and again $\backslash Pi^\_k=\backslash mathrm^\_k=\backslash mathrm^\_k$ if and only if it can be written as ::$x\backslash in\; L\backslash iff\backslash exists\; y\_1\backslash ,\backslash forall\; y\_2\backslash dots\; Qy\_k\backslash ,R(x,y\_1,\backslash dots,y\_k),$ :where $R(x,y\_1,\backslash dots,y\_k)$ is computable in time $2^$ for some ''c'', which again implicitly bounds the length of ''yi''. Equivalently, EXPH is the class of languages computable in time $2^$ on an alternating Turing machine with constantly many alternations. We have E ⊆ NE ⊆ EH ⊆ ESPACE, EXP ⊆ NEXP ⊆ EXPH ⊆ EXPSPACE, and EH ⊆ EXPH. == References == 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「exponential hierarchy」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.